package class29;

/**
 * @author zhangchaoliang
 * create 2022
 */
public class MinPath {

    public static int minPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        return process(matrix, 0, 0);
    }

    private static int process(int[][] matrix, int i, int j) {
        int endi = matrix.length - 1;
        int endj = matrix[0].length - 1;
        if (i > endi || j > endj) {
            return 0;
        }
        if (i == endi && j == endj) {
            return matrix[i][j];
        }

        int down = process(matrix, i + 1, j);
        int right = process(matrix, i, j + 1);
        if (down == 0 && right == 0) {
            return 0;
        }
        down = down == 0 ? Integer.MAX_VALUE : down;
        right = right == 0 ? Integer.MAX_VALUE : right;
        return Math.min(down, right) + matrix[i][j];
    }


    public static int dp(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
        int r = dp.length;
        int c = dp[0].length;
        for (int i = r - 1; i >= 0; i--) {
            for (int j = c - 1; j >= 0; j--) {
                int down = i + 1 < r ? dp[i + 1][j] : 0;
                int right = j + 1 < c ? dp[i][j + 1] : 0;
                if (down == 0 && right == 0) {
                    dp[i][j] = matrix[i][j];
                    continue;
                }
                down = down == 0 ? Integer.MAX_VALUE : down;
                right = right == 0 ? Integer.MAX_VALUE : right;
                dp[i][j] = Math.min(down, right) + matrix[i][j];
            }
        }
        return dp[0][0];
    }

    private static int dp2(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int r = matrix.length;
        int c = matrix[0].length;
        int[][] dp = new int[r][c];
        for (int k = 0; k < r; k++) {
            dp[k][0] = k - 1 >= 0 ? matrix[k - 1][0] + matrix[k][0] : matrix[k][0];
        }
        for (int k = 0; k < c; k++) {
            dp[0][k] = k - 1 >= 0 ? matrix[0][k - 1] + matrix[0][k] : matrix[0][k];
        }
        for (int k = 1; k < r; k++) {
            for (int l = 1; l < c; l++) {
                dp[k][l] = Math.min(dp[k - 1][l], dp[k][l - 1]) + matrix[k][l];
            }
        }
        return dp[r - 1][c - 1];
    }

    public static int dp3(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
        int r = matrix.length;
        int c = matrix[0].length;
        int[] dp = new int[c];
        for (int k = 0; k < c; k++) {
            dp[k] = k - 1 >= 0 ? matrix[0][k - 1] + matrix[0][k] : matrix[0][k];
        }
        for (int i = 1; i < r; i++) {
            dp[0] += matrix[i][0];
            for (int j = 1; j < c; j++) {
                int temp = dp[j];
                dp[j] = Math.min(temp, dp[j - 1]) + matrix[i][j];
            }
        }
        return dp[c - 1];
    }


    public static void main(String[] args) {
        int[][] matrix = new int[][]{
                {1, 2, 3, 4, 5},
                {1, 1, 1, 1, 2},
                {1, 1, 2, 2, 2},
                {4, 1, 2, 8, 1}

        };
        System.out.println("===");
        System.out.println(minPath(matrix));
        System.out.println(dp(matrix));
        System.out.println(dp2(matrix));
        System.out.println(dp3(matrix));
    }


}
